{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "### 北极狐算法是什么？\n",
    "在文章《基于遗传编程自动设计优化算法（自动发现北极狐优化算法）》中，我们利用遗传编程算法在五分钟内发现了一个新的优化算法，$X_{\\text{new}} = X + (F \\cdot X - F)$, 命名为北极狐算法。\n",
    "众所周知，在设计算法的时候，我们不仅仅希望取得良好的实验效果，还希望设计出的算法有理论保证。那么，我们是否可以证明北极狐算法一定收敛到全局最优呢？\n",
    "\n",
    "### 北极狐算法的收敛性\n",
    "**假设：**\n",
    "- $ \\mathcal{S} \\subset \\mathbb{R}^n $ 是一个有界搜索空间，其中包含全局最优解 $ X^* $。\n",
    "- $ F $ 是从某个分布中抽取的随机扰动向量，$ F $ 的取值范围是整个搜索空间 $\\mathcal{S}$。\n",
    "\n",
    "**证明：**\n",
    "定义 $ A_\\epsilon $ 为 $ X^* $ 的 $\\epsilon$-邻域，即 $ A_\\epsilon = \\{ X \\in \\mathcal{S} : \\|X - X^*\\| < \\epsilon \\} $。设 $ P_\\epsilon $ 为一次操作中 $X_{\\text{new}} = X + (F \\cdot X - F)$ 落入 $ A_\\epsilon $ 的概率。因为 $ F $ 能覆盖整个搜索空间，所以即便对于足够小的 $ \\epsilon $，依然可以得到$ P_\\epsilon > 0 $。\n",
    "\n",
    "在 $ N $ 次迭代中，$X_{\\text{new}}$ 至少一次落入 $ A_\\epsilon $ 的概率是 $ 1 - (1 - P_\\epsilon)^N $。使用极限，我们可以表示这个概率在 $ N $ 趋向无穷大时的行为：\n",
    "\n",
    "$$ \\lim_{N \\to \\infty} \\left[ 1 - (1 - P_\\epsilon)^N \\right] = 1 $$\n",
    "\n",
    "这个极限表达了随着迭代次数 $ N $ 的增加，$X_{\\text{new}}$ 至少一次落入 $ X^* $ 的 $\\epsilon$-邻域的概率趋近于 1。\n",
    "\n",
    "### 结论：\n",
    "现在，我们证明了北极狐算法 $X_{\\text{new}} = X + (F \\cdot X - F)$ 在无限次迭代的情况下，能够以概率 1 接近全局最优解 $X^*$。"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "b6c87f3572f1a7aa"
  },
  {
   "cell_type": "code",
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false
   },
   "id": "e64e0268ee5ee8f7"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
